package code.starivan.niuke.jianoffer;

/**
 * Created by Ivan on 2015/8/24.
 */

/*
��Ŀ����

        ����һ���������飬�жϸ������ǲ���ĳ�����������ĺ�������Ľ����
        ����������Yes,�������No���������������������������ֶ�������ͬ��
*/

public class VerifySquenceOfBST {
    public boolean verifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0)
            return false;

        if (sequence.length == 1)
            return true;

        return verifySquenceOfBST(sequence, 0, sequence.length-1);
    }

    private boolean verifySquenceOfBST(int[] sequence, int start, int end) {

        if (start > end)
            return false;
        if (start == end)
            return true;

        int node = sequence[end];
        int index = end - 1;
        while (index >= start && sequence[index] >= node) {
            index--;
        }

        for(int i=index;i>=start;i--){
            if(sequence[i]>=node){
                return  false;
            }
        }

        boolean left, right;
        if (index < start) {
            left = true;
            right = verifySquenceOfBST(sequence, start, end - 1);
        } else {
            left = verifySquenceOfBST(sequence, start, index);
            if(index+1>=end)
                right=true;
            else
                right=verifySquenceOfBST(sequence, index+1, end - 1);
        }

        return left&&right;

    }
}
